package com.algorithm.base.backtracking;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

/**
 * 组合sum3
 * 找出所有相加之和为 n 的 k 个数的组合
 *
 * @author Amadeus
 * @date 2023/10/31
 */
public class CombinationSum3 {

    public List<List<Integer>> combinationSum3(int k, int n) {
        List<List<Integer>> list = new ArrayList<>();
        Deque<Integer> queue = new ArrayDeque<>(9);
        backTracking(n, k, 1, list, queue);
        return list;
    }

    public void backTracking(int n, int k, int i, List<List<Integer>> list, Deque<Integer> queue) {
        if (queue.size() == k) {
            if (n == 0) {
                list.add(new ArrayList<>(queue));
            }
            return;
        }
        if (i + k > 9 || n < 0) {
            return;
        }
        for (int j = i; j <= 10 - (k - queue.size()); j++) {
            n -= j;
            queue.addLast(j);
            backTracking(n, k, j + 1, list, queue);
            n += j;
            queue.removeLast();
        }
    }

}
